package ds;

import ds.exception.EmptyException;
import ds.exception.PosIllegal;

import java.util.Arrays;
import java.util.Comparator;

// 顺序表
public class MyArrayList<T> {
    private Object[] array;
    private int valSize;
    private static final int DEFAULT_CAPACITY = 16;

    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public MyArrayList(int capacity) {
        array = new Object[capacity];
        valSize = 0;
    }

    // 新增元素,默认在数组最后新增
    public void add(T data){
        add(valSize, data);
    }

    // 在 pos 位置新增元素
    public void add(int pos, T data) {
        try {
            checkPos(pos);
            if (isFull()) {
                resize();
            }
            for (int i = size() - 1; i >= pos; i--) {
                array[i + 1] = array[i];
            }
            array[pos] = data;

            valSize ++;
        } catch (PosIllegal e) {
            System.out.println("插入位置不合法！");
            e.printStackTrace();
        }
    }

    // 扩容
    private void resize() {
        int newCapacity = array.length + (array.length >> 1);
        array = Arrays.copyOf(array, newCapacity);
    }

    // 判断顺序表是否满
    public boolean isFull() {
        return valSize == array.length;
    }

    // 判定是否包含某个元素
    public boolean contains(Object toFind) { return indexOf(toFind) >= 0; }

    // 查找某个元素对应的位置
    public int indexOf(Object toFind) {
        if (toFind == null) {
            for (int i = 0; i < valSize; i++) {
                if (array[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < valSize; i++) {
                if (toFind.equals(array[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    // 获取 pos 位置的元素
    public T get(int pos) {
        try {
            checkPos2(pos);
            checkEmpty();

            return array(pos);
        } catch (RuntimeException e) {
            e.printStackTrace();
        }
        return null;
    }

    T array(int index) {
        return (T) array[index];
    }

    // 给 pos 位置的元素设为 value
    public void set(int pos, Object value) {
        try {
            checkPos2(pos);
            checkEmpty();

            array[pos] = value;

        } catch (RuntimeException e) {
            e.printStackTrace();
        }
    }

    //删除第一次出现的关键字key
    public boolean remove(Object toRemove) {
        if (toRemove == null) {
            for (int i = 0; i < valSize; i++) {
                if (array[i] == null) {
                    return true;
                }
            }
        } else {
            for (int i = 0; i < valSize; i++) {
                if (toRemove.equals(array[i])) {
                    for (int j = i + 1; j < valSize; j++) {
                        array[j - 1] = array[j];
                    }
                    valSize --;
                    return true;
                }
            }
        }
        return false;
    }

    public T remove(int index) {
        try {
            checkPos2(index);
            checkEmpty();

            T tmp = array(index);

            for (int i = index; i < valSize - 1; i++) {
                array[i] = array[i + 1];
            }

            valSize --;
            return tmp;
        } catch (RuntimeException e) {
            e.printStackTrace();
        }
        return null;
    }

    // 获取顺序表元素个数
    public int size() { return valSize; }

    // 清空顺序表
    public void clear() {
        valSize = 0;
    }

    // 排序
    public void sort() {
        Arrays.sort(array, 0, valSize);
    }
    public void sort(Comparator<? super T> comparator) {
        Arrays.sort((T[]) array, 0, valSize, comparator);
    }

    private void checkEmpty() {
        if (isFull()) {
            throw new EmptyException("顺序表为空");
        }
    }

    private void checkPos(int pos) {
        if (pos < 0 || pos > valSize) {
            throw new PosIllegal("Pos位置不合法！");
        }
    }
    private void checkPos2(int pos) {
        if (pos < 0 || pos >= valSize) {
            throw new PosIllegal("Pos位置不合法！");
        }
    }

    public boolean isEmpty() {
        return valSize == 0;
    }

    public String toString() {
        if (isEmpty()) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();

        sb.append("[");
        for (int i = 0; i < valSize; i++) {
            sb.append(array(i));
            if (i < valSize - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");

        return sb.toString();
    }
}
